#include <iostream>
#include <bits/stdc++.h>
#include "lib/u.h"

using namespace std;

void qsort(vector<int> v, int l, int r) {

    int i, j, mid, p;
    i = l, j = r;
    mid = v[(l + r) / 2];
    cout << "-------- mid=" << mid << endl;

    do {
        while (v[i] < mid) i++;
        while (v[j] > mid) j--;

        if (i <= j) {
            // swap
            p = v[i];
            v[i] = v[j];
            v[j] = p;

            i++;
            j--;

            PrintVector(v);
        }


    } while (i <= j);

    cout << "****** l=" << l << ", j=" << j << ", i=" << i << ", r=" << r << endl;
    PrintVector(v);

    if (l < j) qsort(v, l, j);
    if (i < r) qsort(v, i, r);

}

int main() {
    vector<int> v = {18, 27, 6, 25, 14, 33, 12, 1};

    PrintVector(v);
    cout << "==============" << endl;
    qsort(v, 0, v.size() - 1);

    return 0;
}